Appearance
const parent = (i - 1) 1;
本节目标:理解“const parent = (i - 1) 1;”的核心思路,并能把它用于实际开发或面试表达。 是在 数组实现的二叉最小堆 中,根据子节点下标 i 计算其父节点下标。
| 细节 | 说明 |
| 二叉堆数组映射 | 0-基索引时: |
| • 左子 = 2 * i + 1 | |
| • 右子 = 2 * i + 2 | |
| • 父 = ⌊(i – 1) / 2⌋ | |
| >> 1 | JavaScript 的有符号右移: |
| 把数字按二进制整体右移 1 位,相当于对正整数做 ⌊x / 2⌋(向下取整的除 2)。 | |
| i – 1 | 先减 1 再除 2,就得 ⌊(i – 1)/2⌋ —— 正是父节点下标。 |
| 为何不用 / 2 | 位移运算比浮点除法更快;>> 会直接给出整数结果,无需 Math.floor()。 |
举例:
- 节点索引 i = 5
- (i - 1) >> 1 = (4) >> 1 = 2 → 父节点索引 2
- i = 1 → (0) >> 1 = 0 → 父就是根节点。
